package com.hyb.algorithm.data.struct.dp;

import com.hyb.algorithm.data.struct.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 337. 打家劫舍 III
 * https://leetcode.cn/problems/house-robber-iii/description/
 * @author: ybhu
 * @create: 2024/01/06 08:41
 */
public class RobIII5 {

    //选中当前node
    Map<TreeNode,Integer> selected=new HashMap<TreeNode,Integer>();
    //不选当前node
    Map<TreeNode,Integer> noSelected=new HashMap<TreeNode,Integer>();

    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);

        root.left=new TreeNode(4);
        root.left.left=new TreeNode(1);
        root.left.right=new TreeNode(3);

        root.right=new TreeNode(5);
        root.right.right=new TreeNode(1);

        int ret=new RobIII5().rob(root);
        System.out.println(ret);

    }



    public int rob(TreeNode root) {
        dfs(root);

        return Math.max(selected.getOrDefault(root,0),noSelected.getOrDefault(root,0));
    }


    public void dfs(TreeNode root){

        if(root==null){
            return;
        }

        dfs(root.left);
        dfs(root.right);

        //选中
        selected.put(root,root.val+noSelected.getOrDefault(root.left,0)+noSelected.getOrDefault(root.right,0));
        //不选中
        noSelected.put(root,Math.max(selected.getOrDefault(root.left,0),noSelected.getOrDefault(root.left,0))+
                Math.max(selected.getOrDefault(root.right,0),noSelected.getOrDefault(root.right,0)));
    }


}
